#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

void PrintArry(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

}

void ShellSort(int* a, int n)
{
	//多次分组
	//gap越大，元素跳动得越大，数组越无序；gap越小，数组越有序
	int gap = n;
	while (gap>1)  //gap>1预排序，gap=1插入排序
	{
		gap /= 2; //gap/3+1；
		//多组交换
		for (int i = 0; i < n - gap; i++)
		{
			//一组的一次交换
			int end = i;
			int temp = a[i + gap];
			while (end >= 0)
			{
				if (temp < a[end])
				{
					a[end + gap] = a[end];
					end-=gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = temp;
		}
		PrintArry(a, n);
	}
}

int main()
{
	int a[] = {9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-6,-8,-8,-9};
	printf("排序前：\n");
	PrintArry(a, sizeof(a) / sizeof(a[0]));

	printf("排序后：\n");
	ShellSort(a, sizeof(a) / sizeof(a[0]));


	return 0;
}